﻿// exercise_7.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <stdio.h>
#include <math.h>

//7-1 交换最大值和最小值
void ex7_7_1()
{
	int n;
	int a[50] = { 0 };
	int min = 0, max = 0;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
		if (a[min] > a[i])
			min = i;
		if (a[max] < a[i])
			max = i;
	}

	printf("max = %d, min = %d\n", a[max], a[min]);

	int temp = a[min];
	a[min] = a[max];
	a[max] = temp;

	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
}

//7-2排序
void ex7_7_2()
{
	int n = 0;
	int a[105];

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
	}

	int flag = 1;
	for (int i = 1; flag && i < n; i++) {
		flag = 0;
		for (int j = 0; j < n - i; j++) {
			if (a[j] > a[j + 1]) {
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				flag = 1;
			}
		}
	}
	printf("%d", a[0]);
	for (int i = 1; i < n; i++) {
		printf(" %d", a[i]);
	}

	printf("\n");
}

//7-3 查找下标最大的目标值
int upper_bound(int a[], int n, int target)
{
	int left = 0, right = n - 1, mid;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (a[mid] == target) {
			left = mid + 1;
		}
		else if (a[mid] > target) {
			right = mid - 1;
		}
		else if (a[mid] < target) {
			left = mid + 1;
		}
	}

	if (right == -1 || a[right] != target)
		return -1;
	return right;
}

void ex7_7_3()
{
	int a[100005] = { 0 };
	int n, k;

	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
	}
	printf("%d", upper_bound(a, n, k));
}

//7-4 输出二进制
void print_binary_shift(int n)
{
	for (int i = 31; i >= 0; i--) {
		printf("%d", (n >> i) & 0x00000001);
		if (i && i % 8 == 0)
			printf(" ");
	}
}

void print_binary_mod(int n)
{
	int a[32] = { 0 };
	//转换为unsigned int 得到n的补码
	unsigned int nu = n;
	for (int i = 31; i >= 0; i--) {
		a[i] = nu % 2;
		nu /= 2;
	}
	for (int i = 0; i < 32; i++)
	{
		printf("%d", a[i]);
		if ((i + 1) % 8 == 0 && i < 31)
			printf(" ");
	}
}
void ex7_7_4()
{
	int n = 0;
	scanf("%d", &n);
	//print_binary_mod(n);
	print_binary_shift(n);
}

//7-5 进制转换
char digits[17] = "0123456789ABCDEF";
void to_base_p(long long n, int p)
{
	if (n < p) {
		putchar(digits[n]);
		return;
	}
	to_base_p(n / p, p);
	putchar(digits[n % p]);
}
void to_base_p_iter(long long n, int p)
{
	char p_str[32] = { 0 };
	int k = 0;

	do {
		p_str[k++] = digits[n % p];
	} while (n /= p);

	for (int i = k - 1; i >= 0; i--) {
		putchar(p_str[i]);
	}
}

void ex7_7_5()
{
	int T;
	long long n;
	int p;

	scanf("%d", &T);

	while (T--) {
		scanf("%lld%d", &n, &p);

		printf("%lld ", n);

		if (n < 0) {
			printf("-");
			n = -n;
		}

		to_base_p(n, p);
		printf("\n");
	}
}

int main()
{
}